1. Field of the Invention
The present invention relates to digital image processing, and in particular, to a method of converting a bitmap image at a given input resolution to a desired output resolution while preserving the original image density and micro-structure detail.
2. Description of Prior Art
One method of representing image information at an image output terminal such as a printer or display is through image bitmaps. A bitmap is a matrix of pixels with the dimensions i.times.J.times.a (width.times.length.times.depth). A pixel is a discrete unit of area identifiable by its position, with a value indicative of its density. Pixel resolution is the degree of detail used to represent an original image, which is measured using a scale of the unit area, I in one dimension and J in another (commonly expressed in spots per inch). Depth b of each pixel describes a gray density or intensity level from white, the absence of color, through black. Typically, a better approximation of an original image is achieved by increasing the pixel density and resolution of its digital representation.
Resolution conversion, i.e., converting a bitmap from first resolution I.times.J.times.a to second resolution M.times.N.times.d, is an important interoperability enabler in distributed printing environments. Distributed environments may require a user to have the ability to create a digital image at one resolution and print, transfer or display at another resolution. Ideally, resolution conversion of bitmap images should appear fast and transparent to a user, while causing no image degradation.
Known methods of resolution conversion provide bit doubling of an original bitmap image, a simple scheme leaving a large number of problems unresolved. Among these problems are image erosion and dilation, which occur when images are optimized for write-white or write-black printers. Erosion occurs when images destined for write-black printers are sent to write-white printers resulting in thinner lines than desired. Another side effect of resolution conversion is halfbitting. Halfbitting optimizations occurs in lower resolution images in order to achieve a higher resolution effect at edges of images. Both halfbitting and erosion and dilation problems occur because bit doubling does not maintain the density of an image over a given area. As a result, artifacts are produced giving a resolution converted image a different appearance from an original.
Methods to convert gray images to binary or another number of levels while attempting to preserve the local density exist in applications separate from resolution conversion. These and similar methods might be applied as one part of the method in resolution conversion. One method, which can be used to prepare an image at a given resolution and level depth of I.times.J.times.a for printing on a printer with resolution M.times.N.times.d, is error diffusion as described in "An Adaptive Algorithm for Spatial Greyscale," by Floyd and Steinberg, Proc. of the S.I.D. 17/2, 75-77 (1976) (hereinafter, "Floyd and Steinberg". Current distributed environments require a greater degree of flexibility from resolution conversion schemes, as the following more recent advances teach.
U.S. Pat. No. 4,651,287 to Tsao and U.S. Pat. No. 4,811,239 to Tsao disclose a technique which uses an error diffusion algorithm to produce high quality images wherein the gray scale values are compared to the discrete gray scale values of a reference printed array to produce a corresponding error array. U.S. Pat. No. 4,668,995 to Chen et al. discloses a quantization error diffusion algorithm for transforming a multi-bit image into a binary image by diffusing a propagation error among neighboring blocks of pixels. U.S. Pat. No. 4,654,721 to Goertzel et al. suggests printing of gray data on a binary printer, where the gray data is normally of a lower resolution and one takes one gray pixel and transfers it into one `dot`, i.e. a number of binary pixels in the output. Goertzel determines the form and location of those dots using error diffusion and edge enhancement. U.S. Pat. No. 4,783,838 to Matsunawa discloses a multi-step technique which first divides the binary image into blocks of pixels in order to generate a gray-tone representation of the image. Image processing and enhancement can be performed on these blocks and the processed blocks are then converted to the output bitmap using a conventional threshold matrix. U.S. Pat. No. 4,742,553 to Irwin teaches mapping of similarly sized input and output pixel groups, and the use of an error passing process to account for thresholding errors in a resolution conversion process.
U.S. Pat. No. 5,051,844 to Sullivan relates to a method for digital halftoning of continuous tone images using error diffusion. The method reduces the appearance of worms by using a human visual system filter to propagate perceived error as opposed to mathematical error. U.S. Pat. No. 5,050,000 to Ng describes an error diffusion technique in which the gray level input data into halftone cells which are further subdivided. U.S. Pat. No. 5,014,333 to Miller et al. describes an image processing system with smooth transition between dither and diffusion processes, where an image processor measures the amount of high spatial frequency content of the local neighborhood around a pixel of interest. U.S. Pat. No. 4,955,065 to Ulichney relates to an image processing system for processing bits representing digitized images to produce images which perceptually approximate the continuous tone image with fewer undesirable artifacts. U.S. Pat. No. 4,891,714 to Klees describes a method of processing halftone images in which a calculated error is diffused to surrounding pixels before comparing with a predetermined threshold. U.S. Pat. No. 5,045,952 to Eschbach describes a method of improving image quality by dynamically adjusting the threshold of an error diffusion algorithm to selectively control the amount of edge enhancement introduced into a binary encoded output.
U.S. Patent application Ser. No. 07/513,415, entitled "Bit-Map Image Resolution Converter" assigned to the same assignee as the present invention, contemplates a method of magnifying, by a predetermined magnification factor (n), the original image pixels in two dimensions. U.S. Patent application Ser. No. 07/588,125, entitled "Bitmap Image Resolution Converter Compensating for Write-White Xerographic Laser Printing" assigned to the same assignee as the present invention, teaches conversion of binary images at a lower resolution to a higher resolution while compensating for image properties optimized for write-black destined for write-white printing systems. U.S. Patent application Ser. No. 07/600,542, entitled "Method for Making Image Conversions with Error Diffusion" assigned to the same assignee as the present invention, teaches conversion of an image by simulating printing of the image by creating a representation of a page at the particular resolution, scaling and orientation. The image is then periodically sampled through the page with an aperture that corresponds to the desired output, with error diffusion used in the quantization process. U.S. Patent application Ser. No. 07/737,297, entitled "Method of Resolution Conversion" assigned to the same assignee as the present invention. The method disclosed determines correlation values for a plurality of input pixels to obtain the intensity of the output pixels.
The pertinent portions of all references cited herein are incorporated by reference for their teachings.